1784D - Wooden Spoon - CodeForces Solution

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
vector<long long> fact, inv_mod;
int mod = 998244353;
long long inv_modul(long long num)
{
	num %= mod;
	int po = mod-2;
	long long ans = 1;
	while(po>0)
	{
		if(po&1)
		{
			ans = (ans*num)%mod;
		}
		num = (num * num)%mod;
		po /= 2;
	}
	return ans;
}
int precomp(int last)
{
	fact.push_back(1); inv_mod.push_back(1);
	for(int i=0; i<last; i++)
	{
		fact.push_back((fact[i]*(i+1))%mod);
		inv_mod.push_back(inv_modul(fact.back()));
	}	
	return 0;
}
long long nCr(long long n, long long r)
{
	if(r<0 || r>n)
	{
		return 0;
	}
	long long ans = fact[n];
	ans = (ans * inv_mod[r])%mod;
	ans = (ans * inv_mod[n-r])%mod;
	return ans;	
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int n;
	cin>>n;
	precomp(1 << n);
	vector<long long> dp(1 << n);
	dp[0] = ((1 << n) * (fact[1 << (n-1)]))%mod; 		//going for keeping in 2^n ways and going down from fun(a0,0), a0=1
						   
	for(int i=n-2; i>=0; i--)
	{
		long long sum = 0;
		vector<long long> new_dp(1 << n); 		 
		for(int j=0; j<(1<<n); j++)
		{
			new_dp[j] =  (nCr((1<<n) - j - 1 -(1<<i), (1<<i) - 1)*sum)%mod;
			new_dp[j] = (new_dp[j] * fact[1<<i])%mod;
			sum = (sum+dp[j])%mod;
		}
		dp = new_dp;	
	}
	//final touch going for i=n and printing combinatoral fun() = 1 at this point only dp's to be summed
	long long sum = 0;
	for(int i=0; i<(1<<n); i++)
	{
		cout<<sum<<endl;
		sum = (sum+dp[i])%mod;	
	}
	return 0;	
}
//note to outline
//let's try to find the cases where an an-1 clash then an-1 an-2 clash and so on... for some given a ish pairs
	/*let me place an in the tournament in 2^n ways, I will have only one spot to land an-1
		 i.e. besides an
	Now, an-2 must win the second round against an-1 so it must be placed somewhere in the definite neighbourhood of 2
	wrt an-1, and it must win a game against someone in the first round and that must be a bigger no. player. and must
	not be an-1, an (both of which have to be bigger) alors,
		2^n - an-2 - 2 ways or (2^n - an-2 - 2)C1 way and rearranging in 2 ways.
	Now, an-3 must win the third round but it must defeat a person and another person who defeated another person.
	must be paired with 3 other larger numbers (must not be an, an-1, an-2, loser to an-2).
		(2^n - an-3 - 4)C3 ways and rearranging in 4! ways.
	must not be difficult to notice
		(2^n - an-i - 2^(i-1))C(2^(i-1)-1) ways and rearranging in (2^(i-1))! ways.
		(2^n - ai - 2^(n-i-1))C(2^(n-i)
	so on....... at i=n the combantion term becomes 1 and there's just (2^(n-1))! 
	so.
	I need to sum all such products (for diff pairs of a0,a1,a2...an (a0=1 is the only possible thing btw))!
	how do I do that well let's call these fun(ai, i) = combo*rearrange and all that stuff and dp it  
		*/